#include <bits/stdc++.h>
#define int long long
namespace scd {
using namespace std;
template <typename Raw = int, typename T = decay_t<Raw>>
inline auto read() -> enable_if_t<is_integral<T>::value, T> {
    T x = 0;
#ifdef USE_IOSTREAM
    cin >> x;
#else
    bool fl = false;
    char c = getchar();
    while (c < '0' || c > '9')
        fl |= (c == '-'), c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return fl ? -x : x;
#endif
    return x;
}
template <typename Raw, typename T = decay_t<Raw>>
inline auto read() -> enable_if_t<!is_integral<T>::value, T> {
    T x;
    cin >> x;
    return x;
}
template <typename Raw, typename T = decay_t<Raw>>
inline auto read(Raw&& x) -> enable_if_t<is_integral<T>::value> {
#ifdef USE_IOSTREAM
    cin >> x;
#else
    x = 0;
    bool fl = false;
    char c = getchar();
    while (c < '0' || c > '9')
        fl |= (c == '-'), c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
#endif
}
inline void read(char* p) {
#ifdef USE_IOSTREAM
    cin >> p;
#else
    char c = getchar();
    while (isspace(c))
        c = getchar();
    while (c != EOF && !isspace(c)) {
        *p++ = c;
        c = getchar();
    }
    *p = '\0';
#endif
}
template <typename T>
inline auto read(T&& x) -> enable_if_t<!is_integral<decay_t<T>>::value> {
    cin >> x;
}
template <typename... T>
inline void read(T&&... x) {
    (read(forward<T>(x)), ...);
}
template <typename Raw = int, typename T = decay_t<Raw>>
inline auto print(Raw x) -> enable_if_t<is_integral<T>::value> {
#ifdef USE_IOSTREAM
    cout << x;
#else
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
#endif
}
template <int d = 6, typename Raw = double, typename T = decay_t<Raw>>
inline auto print(Raw x) -> enable_if_t<is_floating_point<T>::value> {
#ifdef USE_IOSTREAM
    cout.precision(d);
    cout << std::fixed << x;
#else
    printf("%.*f", d, x);
#endif
}
inline void print(char x) {
#ifdef USE_IOSTREAM
    cout.put(x);
#else
    putchar(x);
#endif
}
inline void print(const char* x) {
#ifdef USE_IOSTREAM
    cout << x;
#else
    while (*x)
        putchar(*x++);
#endif
}
template <typename Raw, typename T = decay_t<Raw>>
inline auto print(Raw&& x)
    -> enable_if_t<!is_integral<T>::value && !is_floating_point<T>::value> {
    cout << x;
}
template <typename... T>
inline void print(T&&... x) {
    (print(forward<T>(x)), ...);
}
template <typename... T>
inline void printws(T&&... x) {
    (print(forward<T>(x), ' '), ...);
}
template <typename... T>
inline void println(T&&... x) {
    printws(x...);
    print('\n');
}
}  // namespace scd
using namespace scd;
namespace dfs {
int n, m, q, k, res, a[5], b[5];
void doit(int p) {
    if (p > q) {
        for (int i = 1; i + m - 1 <= n; ++i) {
            auto ch = [&] {
                for (int j = 1; j <= m; ++j)
                    if (a[i + j - 1] != b[j])
                        return 0;
                return 1;
            };
            if (ch())
                ++res;
        }
        return;
    }
    for (int pos = 1; pos <= n; ++pos)
        for (int i = 1; i <= k; ++i) {
            int lst = a[pos];
            a[pos] = i;
            doit(p + 1);
            a[pos] = lst;
        }
}
}  // namespace dfs
constexpr int N = 3e6 + 5, mod = 998244353;
int n, m, q, k, a[N];
inline int qpow(int x, int k) {
    int res = 1;
    while (k) {
        if (k & 1)
            res = res * x % mod;
        x = x * x % mod;
        k >>= 1;
    }
    return res;
}
inline int inv(int x) {
    return qpow(x, mod - 2);
}
inline int factorial(int n) {
    int res = 1;
    while (n--)
        res = res * (n + 1) % mod;
    return res;
}
inline int A(int n, int m) {
    return factorial(n) * inv(factorial(n - m)) % mod;
}
inline int Mod(int x) {
    return x >= mod ? x - mod : x;
}
int32_t main(int32_t argc, const char** argv) {
    freopen("sequence.in", "r", stdin);
    freopen("sequence.out", "w", stdout);
    read(n, m, q, k);
    if (q < m) {
        println(0);
        return 0;
    }
    if (max({n, m, q, k}) <= 4) {
        dfs::n = n;
        dfs::m = m;
        dfs::q = q;
        dfs::k = k;
        for (int i = 1; i <= m; ++i)
            read(dfs::b[i]);
        dfs::doit(1);
        println(dfs::res);
        return 0;
    }
    int sum = A(q, m) * (n - m + 1) % mod;
    int res = qpow((n - m) * k, q - m) * sum % mod;
    int lim = min(m, q - m);
    for (int i = 1; i <= lim; ++i)
        res = Mod(res +
                  qpow((n - m) * k, q - m - i) * qpow(m, i) % mod * sum % mod);
    println(res);
    return 0;
}